#include <iostream>
using namespace std;
#define MOD (int)(1e9+7)
struct pid {
	int prepre;
	int pre;
	int cur;
};
int fib(int n) {
	if (n < 2) { return n; }
	pid a;
	a.prepre = 0;
	a.pre = 1;
	for (int i = 2; i <= n; ++i) {
		a.cur = (a.prepre + a.pre)%MOD;
		a.prepre = a.pre;
		a.pre = a.cur;
	}
	return a.cur;
}
void test(int n, int exp) {
	int ans = fib(n);
	if (ans == exp) {
		cout << "passed!" << endl;
	}
	else {
		cout << "failed!" << endl;
	}
}
int main() {
	test(0, 0);
	test(1, 1);
	test(2, 1);
	test(3, 2);
	test(4, 3);
	test(5, 5);
	test(6, 8);
	test(7, 13);
	test(8, 21);
	test(9, 34);
	test(10, 55);
}